// https://leetcode.cn/problems/domino-and-tromino-tiling/

/*
动态规划的思路：
最后一排铺满的情况：
1.前一排铺满 f[i-1][0] 只能加一排竖的
2.前一排上方铺了，下面是空的 f[i-1][1] 只能加个倒的L
3.前一排下方铺了，上面是空的 f[i-1][2] 只能加个反的L
4.前一排是空的f[i-1][3] 两个横的 注意：加两个竖的的会和1的状态重合，所以不能加两个竖
f[i][0] = f[i-1][0] + f[i-1][1] + f[i-1][2] + f[i-1][3]

最后一排上方铺了的情况：
1.前一排铺满 f[i-1][0] 【这种情况不能构成，忽略】
2.前一排上方铺了，下面是空的 【这种情况不能构成，忽略】
3.前一排下方铺了，上面是空的 f[i-1][2] 上方加个横条
4.前一排是空的f[i-1][3] 后面加个旋转的L
f[i][1] = f[i-1][2] + f[i-1][3]

后面两种情况可以推得
f[i][2] = f[i-1][1] + f[i-1][3]
f[i][3] = f[i-1][0] 这里为什么没有加上f[i-1][3]的原因是如果加了，就等同与前一排加了一个竖，是重复计算

*/
#include <vector>
#include <iostream>
using namespace std;
class Solution
{
public:
    int numTilings1(int n)
    {
        int MOD = 1e9 + 7;
        vector<vector<long>> dp(n + 1, vector<long>(4));
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[0][3] = 0;
        for (int i = 1; i <= n; i++)
        {
            dp[i][0] = (dp[i - 1][0]) % MOD + (dp[i - 1][1]) % MOD + (dp[i - 1][2]) % MOD + (dp[i - 1][3]) % MOD;
            dp[i][1] = (dp[i - 1][2]) % MOD + (dp[i - 1][3]) % MOD;
            dp[i][2] = (dp[i - 1][1]) % MOD + (dp[i - 1][3]) % MOD;
            dp[i][3] = (dp[i - 1][0]) % MOD;
        }
        return dp[n][0] % MOD;
    }

    int numTilings(int n)
    {
        int MOD = 1e9 + 7;
        vector<long> dp = {1, 0, 0, 0};
        for (int i = 1; i <= n; i++)
        {
            vector<long> tmp(4);
            tmp[0] = dp[0] % MOD + dp[1] % MOD + dp[2] % MOD + dp[3] % MOD;
            tmp[1] = dp[2] % MOD + dp[3] % MOD;
            tmp[2] = dp[1] % MOD + dp[3] % MOD;
            tmp[3] = dp[0] % MOD;
            dp = tmp;
        }
        return dp[0] % MOD;
    }
};